#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <string>
#include <stack>
#include <algorithm>
using namespace std;

class Solution {
public:
    int longestValidParentheses(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		
		if(s.size() < 2)
			return 0;

        std::stack<size_t> pos;
		size_t maxLen = 0;
		for(size_t i =0;i<s.size();i++)
		{
			if(s[i] == '(')
				pos.push(i);
			else if(pos.empty() || s[pos.top()] == ')')
			{
				pos.push(i);
			}
			else
				pos.pop();
		}

		if(pos.empty())
			maxLen = s.size();
		else
		{
			size_t lastPos = s.size();
			do
			{
				maxLen = max(maxLen,lastPos-pos.top()-1);
				lastPos = pos.top();
				pos.pop();
			}while(!pos.empty());
			maxLen = max(maxLen,lastPos);
		}


		return (int)maxLen;
    }
};

#endif
